Data compression occurs in a number of contexts. It is very commonly used in communications and computer networking to store, transmit, and reproduce information efficiently. It finds particular application in the encoding of images, audio and video. Video presents a significant challenge to data compression because of the large amount of data required for each video frame and the speed with which encoding and decoding often needs to occur. The current state-of-the-art for video encoding is the ITU-T H.264/AVC video coding standard. It defines a number of different profiles for different applications, including the Main profile, Baseline profile and others. A next-generation video encoding standard is currently under development through a joint initiative of MPEG-ITU: High Efficiency Video Coding (HEVC).
There are a number of standards for encoding/decoding images and videos, including H.264, that use block-based coding processes. In these processes, the image or frame is divided into blocks, typically 4×4 or 8×8, and the blocks are spectrally transformed into coefficients, quantized, and entropy encoded. In many cases, the data being transformed is not the actual pixel data, but is residual data following a prediction operation. Predictions can be intra-frame, i.e. block-to-block within the frame/image, or inter-frame, i.e. between frames (also called motion prediction). It is expected that HEVC will also have these features.
When spectrally transforming residual data, many of these standards prescribe the use of a discrete cosine transform (DCT) or some variant thereon. The resulting DCT coefficients are then quantized using a quantizer to produce quantized transform domain coefficients, or indices.
The block or matrix of quantized transform domain coefficients (sometimes referred to as a “transform unit”) is then entropy encoded using a particular context model. In H.264/AVC and in the current development work for HEVC, the quantized transform coefficients are encoded by (a) encoding a last significant coefficient position indicating the location of the last non-zero coefficient in the block, (b) encoding a significance map indicating the positions in the block (other than the last significant coefficient position) that contain non-zero coefficients, (c) encoding the magnitudes of the non-zero coefficients, and (d) encoding the signs of the non-zero coefficients. This encoding of the quantized transform coefficients often occupies 30-80% of the encoded data in the bitstream.
Transform units are typically N×N. Common sizes include 4×4, 8×8, 16×16, and 32×32, although other sizes are possible, including non-square sizes in some embodiments, such as 8×32 or 32×8. The entropy encoding of the symbols in the significance map is based upon a context model. In the case of 4×4 or 8×8 luma or chroma blocks or transform units (TU), a separate context is associated with each coefficient position in the TU. The encoder and decoder must keep track of and look up a large number of different contexts during the encoding and decoding of the significance map. In the case of larger TUs, the context for encoding a significant flag may depend on the values of neighbouring significance flags. For example, the flag may have a context selected from four or five contexts depending on the values of neighbouring flags. In some instances, particular flags within a TU or sub-block of a TU may have a context based on position, such as the upper-left (DC) position.
The determination of context for the 16×16 and 32×32 significance maps is fairly computationally intense, because in most cases the processor determines context by looking at the values of neighboring significant flags, which involves costly memory access operations.
A binary arithmetic coding (BAC) engine has three stages: context determination or derivation, binary arithmetic coding (encoding or decoding), and probability estimate update. A non-pipelined BAC engine processes a binary symbol by completing all three stages before starting on the next symbol. A pipelined BAC engine attempts to start the next symbol before the current symbol has completed processing through all three stages.
Because context for a significant-coefficient flag is determined by the values of neighboring flags, the processing of a neighboring flag must be completed before it is used to determine context of a current flag, since its processing can impact the probability estimate for a particular context. Thus, it is difficult to maximize throughput per cycle when working with larger significance maps. Attempts to pipeline within the BAC engine can run into stalls.
Similar reference numerals may have been used in different figures to denote similar components.